/**
 * Path 
 * Define Path objects
 **/
var Path = function() {

	this.init = function() {			
		this.pathway = new Array();
		this.openList = new Array();
		this.closedList = new Array();
		this.start = null;
		this.target = null;
	}

	this.getPath = function(start, target) {

		log('Get Path');
		this.init();		

		this.start = start;
		this.target = target;

		// Clean lists
		// game.mMap.clear();
		// Player current cell
		var pCell = game.mMap.getCell({x:this.start.x, y:this.start.y});
		this.openList.push(pCell);
		// Boolean to know if we have reached the target
		var reached = false;

		do {
			// 1 - Begin at the starting point A and add it to an “open list” of squares to be considered
			var startCell = this.openList[0];
			// startCell.highlight = true;

			// 2 - Drop player current cell from open list
			this.closedList.push(this.openList[0]);
			if (distance(this.openList[0].position, this.start))
				this.pathway.push(this.openList[0]);
			this.openList.splice(0,1);

			// 3 - Check neighborhood
			var reached = this.checkNeighborhood(startCell);

			// 4 - Sort the list
			this.sortList(this.openList);

			// 5 - Choose a new cell to start
			// startCell.highlight = false;
		} while (!reached && this.closedList.length < game.mMap.getConf().mapSize.w*2);

		if (reached) {
			// this.openList[0].highlight = true;
			this.closedList.push(this.openList[0]);
			if (distance(this.openList[0].position, this.start))
				this.pathway.push(this.openList[0]);
			this.openList.splice(0,1);

			this.cleanPath();
		}
	}

	this.cleanPath = function() {
		// TODO
		// Faire en sorte que chaque case soit lié à la précédente

		var newPath = new Array;
		var indexP = this.pathway[0].path.P.getX()+','+this.pathway[0].path.P.getY();
		newPath[indexP] = this.pathway[0];

		for (var i = 1; i < this.pathway.length; i++) {
			indexP = this.pathway[i].path.P.getX()+','+this.pathway[i].path.P.getY();
			if (newPath[indexP] == undefined) {
				newPath[indexP] = this.pathway[i];
			}
		};

		this.pathway = new Array();

		for (x in newPath) {
			this.pathway.push(newPath[x]);
		}
	}

	this.checkList = function(cell, list) {
		var found = false;
		for (var i = 0; i < list.length; i++) {
			if (distance(list[i].position, cell.position) == 0) {
				found = true;
				break;
			}
		};
		return found;
	}

	this.checkNeighborhood = function(cell) {
		var cX = cell.getX();
		var cY = cell.getY();
		var reached = false;

		for (var i = cX-1; i <= cX+1; i++) {
			for (var j = cY-1; j <= cY+1; j++) {
				if (!(i == cX && j == cY)) {

					checkedCell = game.mMap.getCell({x:i, y:j});

					if ( checkedCell != undefined && checkedCell.isWalkable() && !this.checkList(checkedCell, this.closedList)) {
						if (!this.checkList(checkedCell, this.openList)) {
							this.openList.push(checkedCell);
							// Set G
							checkedCell.path.G = Math.floor(distance(cell.position,checkedCell.position) * 10);
							// checkedCell.path.G = 10;
							// Set H
							checkedCell.path.H = Math.floor(distance(checkedCell.position,this.target) * 10);
							checkedCell.setParent(cell);
						}
						else {
							if (Math.floor(distance(cell.position,checkedCell.position) * 10) < checkedCell.path.G) {
								// Set G
								checkedCell.path.G = Math.floor(distance(cell.position,checkedCell.position) * 10);
								// checkedCell.path.G = 10;
								// Set H
								checkedCell.path.H = Math.floor(distance(checkedCell.position,this.target) * 10);
								checkedCell.setParent(cell);
							}
						}
						if (distance(checkedCell.position, this.target) == 0 && !reached)
							reached = true;
					}
				}

				if (reached)
					break;
			};
			if (reached)
				break;
		};

		return reached;
	}

	// partitionner(tableau T, premier, dernier, pivot)
	// 	échanger T[pivot] et T[dernier]
	// 	j := premier
	// 	pour i de premier à dernier - 1
	// 		si T[i] <= T[dernier] alors
	// 			échanger T[i] et T[j]
	// 			j := j + 1
	// 	échanger T[dernier] et T[j]
	// 	renvoyer j
	this.getSubArray = function(a, first, last, pivot) {
		a.swap(pivot, last);

		var j = first;
		for (var i = first; i < last; i++) {
			if (a[i].getF() <= a[last].getF()) {
				a.swap(i, j);
				j++;
			}
		}

		a.swap(last, j);

		return j;
	}

	// tri_rapide(tableau t, entier premier, entier dernier)
	// 	début
	// 		si premier < dernier alors
	// 			pivot := choix_pivot(t,premier,dernier)
	// 			pivot := partitionner(t,premier, dernier,pivot)
	// 			tri_rapide(t,premier,pivot-1)
	// 			tri_rapide(t,pivot+1,dernier)
	// 		fin si
	// 	fin
	this.quickSort = function(a, first, last) {
		if (first < last) {
			var pivot = Math.round(rand(first, last));
			pivot = this.getSubArray(a, first, last, pivot);
			this.quickSort(a, first, pivot-1);
			this.quickSort(a, pivot+1, last);
		}
	}

	this.sortList = function(list) {
		// Quicksort on list
		this.quickSort(list, 0, list.length-1);
	}

	this.getNextMove = function(position) {
		var pos = position;
		if (this.pathway[0] != undefined) {
			// if (distance(this.position,this.pathway[0].position) < 1.5)
			pos = this.pathway[0].position;
			this.pathway.splice(0,1);
		}

		return pos;
	}
};